package algorithm.shipinke;


import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，它使用一张字符出现频度表，根据它来构造一种将每个字符表示成二进制串的最优方式，一般可压缩掉20%~90%。
 * |---------+-----+-----+-----+-----+------+------|
 * | letter  |   a |   b |   c |   d |    e |    f |
 * |---------+-----+-----+-----+-----+------+------|
 * | count   |  45 |  13 |  12 |  16 |    9 |    5 |
 * | code    | 000 | 001 | 010 | 011 |  100 |  101 |
 * | huffman |   0 | 101 | 100 | 111 | 1101 | 1100 |
 * |---------+-----+-----+-----+-----+------+------|
 * 如上表所示，假设一篇文章包含45个字母a、13个字母b……，如果用长度相同的编码000、001等去存储这些信息，则需要（45＋13＋12＋16＋9＋5）×3＝300位空间。
 * 但如果换成可变长编码，即编码长度不固定的霍夫曼编码，则仅需要45×1＋13×3＋12×3＋16×3＋9×4＋5×4＝224位空间。
 * 现在给你这些原始数据，请你计算改用霍夫曼编码之后需要多少位空间。
 * 输入描述
 * 输入包含多组数据，每组数据第一行包含一个正整数n（2≤n≤50），表示字符的数量。
 *
 * 第二行包含n个正整数，分别表示这n个字符出现的次数，每个字符出现次数不超过10000。
 * 输出描述
 * 对应每一组数据，输出使用霍夫曼编码需要多少位空间存储这些信息。
 * 示例1
 * 输入
 * 6
 * 45 13 12 16 9 5
 * 输出
 * 224
 */


public class Huffman {

    public int getBit(int n, int[] ary) {
        HNode root = build(ary);
        Map<Integer, Integer> memo = new HashMap<>();
        traverse(root, 0, memo);
        int res = 0;
        for (Map.Entry<Integer, Integer> entry : memo.entrySet()) {
            res += entry.getKey()*entry.getValue();
        }
        return res;
    }

    public void traverse(HNode node, int height, Map<Integer, Integer> map) {
        if (node == null) return;

        if (node.left == null && node.right == null) {
            map.put(node.val, height);
        }
        traverse(node.left, height+1, map);
        traverse(node.right, height+1, map);
    }

    public HNode build(int[] ary) {
        PriorityQueue<HNode> pq = new PriorityQueue<>((o1, o2) -> o1.val-o2.val);
        for (int i : ary) {
            pq.add(new HNode(i));
        }

        while (pq.size() > 1) {
            HNode left = pq.poll();
            HNode right = pq.poll();
            HNode hNode = new HNode(right.val + left.val);
            hNode.left = left;
            hNode.right = right;
            pq.add(hNode);
        }
        return pq.poll();
    }

    static class HNode {
        public int val;
        public HNode left;
        public HNode right;
        public HNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "HNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public static void main(String[] args) {
        Huffman huffman = new Huffman();
        System.out.println(huffman.getBit(6, new int[]{45, 13, 12, 16, 9, 5}));
    }

}
